//===----------------------------------------------------------------------===//
//
//                         CMU-DB Project (15-445/645)
//                         ***DO NO SHARE PUBLICLY***
//
// Identification: src/page/b_plus_tree_leaf_page.cpp
//
// Copyright (c) 2018, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#include <sstream>

#include "common/exception.h"
#include "common/rid.h"
#include "storage/page/b_plus_tree_leaf_page.h"

namespace bustub {

/*****************************************************************************
 * HELPER METHODS AND UTILITIES
 *****************************************************************************/

/**
 * Init method after creating a new leaf page
 * Including set page type, set current size to zero, set page id/parent id, set
 * next page id and set max size
 */
INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_LEAF_PAGE_TYPE::Init(page_id_t page_id, page_id_t parent_id, int max_size) {
  this->SetPageId(page_id);
  this->SetParentPageId(parent_id);
  this->SetNextPageId(INVALID_PAGE_ID);
  this->SetMaxSize(max_size);
  this->SetSize(0);
  this->SetPageType(IndexPageType::LEAF_PAGE);
}

/**
 * Helper methods to set/get next page id
 */
INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::GetNextPageId() const -> page_id_t { return next_page_id_; }

INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_LEAF_PAGE_TYPE::SetNextPageId(page_id_t next_page_id) { next_page_id_ = next_page_id; }

/*
 * Helper method to find and return the key associated with input "index"(a.k.a
 * array offset)
 */
INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::KeyAt(int index) const -> KeyType {
  // replace with your own code
  return array_[index].first;
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::ValueAt(int index) const -> ValueType { return array_[index].second; }
INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::SetKVAt(int index, const KeyType &key, const ValueType &value) -> void {
  array_[index] = MappingType(key, value);
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::Insert(const KeyType &key, const ValueType &value, const KeyComparator &comparator)
    -> bool {
  int size = GetSize();
  // if key exists return false,otherwise, insert into array_
  int left = 0;
  int right = size - 1;
  bool is_exists = false;
  while (left <= right) {
    int mid = (left + right) / 2;
    int ret = comparator(key, array_[mid].first);
    if (ret == 0) {
      is_exists = true;
      break;
    }
    if (ret > 0) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  if (is_exists) {
    return false;
  }
  for (int i = size; i > left; i--) {
    array_[i] = array_[i - 1];
  }
  array_[left] = MappingType(key, value);
  IncreaseSize(1);
  return true;
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::FindKey(const KeyType &key, ValueType &value, const KeyComparator &comparator)
    -> bool {
  // 二分查找
  int left = 0;
  int right = GetSize() - 1;
  bool is_found = false;
  while (left <= right) {
    int mid = (left + right) / 2;
    int ret = comparator(array_[mid].first, key);
    if (ret == 0) {
      is_found = true;
      value = array_[mid].second;
      break;
    }
    if (ret == -1) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return is_found;
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::MappingAt(int index) -> MappingType & { return array_[index]; }

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::Remove(const KeyType &key, const KeyComparator &comparator) -> bool {
  int left = 0;
  int right = GetSize() - 1;
  bool is_removed = false;
  while (left <= right) {
    int mid = (left + right) / 2;
    int ret = comparator(key, array_[mid].first);
    if (ret == 1) {
      left = mid + 1;
    } else if (ret == -1) {
      right = mid - 1;
    } else {
      is_removed = true;
      for (int i = mid; i < GetSize() - 1; i++) {
        array_[i] = array_[i + 1];
      }
      break;
    }
  }
  if (is_removed) {
    DecreaseSize(1);
    return true;
  }
  return false;
}

// INDEX_TEMPLATE_ARGUMENTS
// auto B_PLUS_TREE_LEAF_PAGE_TYPE::Spilt(const KeyType &key, ValueType &value, const KeyComparator &comparatpr) -> void
// { BPlusTreePage *tree_page = this; Recursively split nodes up while (true) {
//   Page *new_leaf_page =
// }
// }

template class BPlusTreeLeafPage<GenericKey<4>, RID, GenericComparator<4>>;
template class BPlusTreeLeafPage<GenericKey<8>, RID, GenericComparator<8>>;
template class BPlusTreeLeafPage<GenericKey<16>, RID, GenericComparator<16>>;
template class BPlusTreeLeafPage<GenericKey<32>, RID, GenericComparator<32>>;
template class BPlusTreeLeafPage<GenericKey<64>, RID, GenericComparator<64>>;
}  // namespace bustub
